//
// Description: 64. 最小路径和
// Created by Loading on 2022/4/5.
//

#include <bits/stdc++.h>

using namespace std;

int minPathSum(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    // dp[i][j] 表示以i, j为终点的路径最小值，注意下标错位
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i < n; ++i) {
        dp[1][i + 1] = dp[1][i] + grid[0][i];
    }
    for (int i = 0; i < m; ++i) {
        dp[i + 1][1] = dp[i][1] + grid[i][0];
    }

    for (int i = 2; i <= m; ++i) {
        for (int j = 2; j <= n; ++j) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }

    return dp[m][n];
}

int main() {
    vector<vector<int>> grid{{1, 3, 1},
                             {1, 5, 1},
                             {4, 2, 1}};
    int res = minPathSum(grid);
    cout << res << endl;

    return 0;
}